package com.dyz.leetcode._20_dynamicProgramming._139;

import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class wordBreak03 {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> dict = new HashSet<>(wordDict);

        boolean[] dp = new boolean[s.length()+1];

        //  初始化
        // 因为空字符串总是字典的一部分。dp 数组剩余的元素都初始化为 false
        dp[0] = true;
        //  定义状态，dp[i] 表示以第 i 个字符结尾的子串是否可以被空格拆分成字典中出现的单词
        for (int i = 1; i <= s.length(); i++) {
            for (int j = i-1; j >=0 ; j--) {
                if(!dict.contains(s.substring(j, i))){continue;}
                if(dp[j]){
                    dp[i] = true;
                    break;
                }

            }

        }
        return dp[s.length()];
    }
}
